package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author wanwei
 * @since 2022-03-16 15:08
 */
public class AU79单词搜索 {

    public static void main(String[] args) {
        char[][] board = {{'a','a','b','a','a','b'},{'a','a','b','b','b','a'},{'a','a','a','a','b','a'},{'b','a','b','b','a','b'},{'a','b','b','a','b','a'},{'b','a','a','a','a','b'}};
        String word = "bbbaabbbbbab";
        System.out.println(exist(board, word));
    }


    public static boolean exist(char[][] board, String word) {
        boolean[][] board2 = new boolean[board.length][board[0].length];

        int total = board[0].length * board.length;
        if (word.length() > total) {
            return false;
        }
        List<Character> listUnique = new ArrayList<>();
        for (int i = 0; i < board[0].length; i++) {
            for (int j = 0; j < board.length; j++) {
                listUnique.add(board[j][i]);
            }
        }
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int index = listUnique.indexOf(chars[i]);
            if (index < 0) {
                return false;
            }
            listUnique.remove(index);
        }

        for (int i = 0; i < board[0].length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[j][i] == word.charAt(0)) {
                    if (exist(board, word, i, j, 0, board2)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }


    /**
     * 压栈 上左下右 直到整个word都被匹配 不能走回头路！！！！！！ 需要记录已走的路线
     * 1.先找到第一个开始的坐标
     * <p>
     * <p>
     * 剪枝
     * 1.单词长度超过总的数组长度
     * 2.如果数组字符 不能全包含单词字符 直接返回false
     *
     * @param board
     * @param word
     * @return
     */
    public static boolean exist(char[][] board, String word, int x, int y, int begin, boolean[][] board2) {
        if (x < 0 || x == board[0].length) {
            return false;
        }
        if (y < 0 || y == board.length) {
            return false;
        }
        if(board2[y][x]){
            return false;
        }
        if (board[y][x] != word.charAt(begin)) {
            return false;
        }
        //匹配到最后一个字符了 则返回true;
        if (word.length() - 1 == begin) {
            return true;
        }
        board2[y][x] = true;

        int xNew = 0;
        int yNew = 0;
        int index = 0;
        while (index < 4) {
            index++;
            switch (index) {
                case 1:
                    xNew = x;
                    yNew = y - 1;
                    break;
                case 2:
                    xNew = x + 1;
                    yNew = y;
                    break;
                case 3:
                    xNew = x;
                    yNew = y + 1;
                    break;
                case 4:
                    xNew = x - 1;
                    yNew = y;
                    break;
            }
            if (exist(board, word, xNew, yNew, begin + 1, board2)) {
                return true;
            }
        }
        board2[y][x] = false;
        return false;
    }
}
